剑指Offer题解 - Day29

剑指 Offer 58 - I. 翻转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。

示例 1：

输入: "the sky is blue"
输出:"blue is sky the"

说明：

• 无空格字符构成一个单词。
• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
• 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

思路：

首先考虑使用原生API进行暴力求解。根据题目说明，要去除前后和中间的多余空格，那么可以分别使用trim和replace 方法进行去除，其中replace使用正则替换多余的空格。

然后分割为数组后翻转，同时合并为新的字符串并返回。

暴力法

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    return s.trim().replace(/\x20+/g, ' ').split(' ').reverse().join(' ');
};

• 时间复杂度 O(n)。
• 空间复杂度 O(n)。

分析：

虽然暴力法可以进行求解，但是真正的面试中不建议使用该方法，只能作为额外的思路进行说明。

双指针

本题可以采取双指针的方法进行求解。

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    s = s.trim(); // 去除首尾空格
    let i = s.length - 1; // 初始化单词的左边界
    let j = i; // 初始化单词的右边界
    let result = []; // 初始化结果数组
    while(i >= 0) { // 单词的左边界小于0则终止循环
        while(i >= 0 && s[i] !== ' ') i--; // 寻找单词的左边界
        result.push(s.slice(i + 1, j + 1)); // 将单词放至结果数组
        while(i >= 0 && s[i] === ' ') i--; // 跳过单词之间的空隙
        j = i; // 重置单词的右边界
    }
    return result.join(' '); // 结果数组拼接为字符串后返回
};

• 时间复杂度 O(n)。
• 空间复杂度 O(n)。

分析：

首先需要去除字符串的首尾空格。

然后声明两个指针分别用来指向单词的左边界和右边界。

然后进行字符串的倒序循环。首先保持右边界不动，寻找每个单词的左边界，直到遇到空格。此时截取s.slice(i + 1, j + 1) 并放至结果数组。然后寻找下一个单词的右边界，重置右边界的索引。

倒序加上单词左右边界，可以将字符串以单词进行分割，同时起到翻转单词的效果。最终将结果数组拼接为字符串并返回即可。

总结

此题优先使用双指针进行求解。需要额外注意的是字符串截取单词的那一行代码。

由于slice方法是左闭右开，而寻找完单词的左边界时，执行了i-- ，因此第一个参数需要i + 1 ；而单词的右边界是j，但是不包含j，因此第二个参数需要j + 1 。

在实现上就体现为：i指针不断的左移，当找到单词的左边界时，就将单词放至结果数组；当找到下一个单词的右边界时，重置单词的右边界j指针。进入下一次循环，重复上述逻辑，直到i < 0。